package com.yun.algorithmproblem.leetcode;

import java.util.ArrayList;
import java.util.HashMap;

public class Leetcode2080 {

    static class RangeFreqQuery {

        HashMap<Integer, ArrayList<Integer>> cnt = new HashMap<>();

        public RangeFreqQuery(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                cnt.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
            }
        }

        public int query(int left, int right, int value) {
            if (!cnt.containsKey(value)) {
                return 0;
            }
            ArrayList<Integer> arrayList = cnt.get(value);
            return querySort(right, arrayList) - querySort(left - 1, arrayList);
        }

        private int querySort(int target, ArrayList<Integer> arrayList) {
            int left = 0;
            int right = arrayList.size() - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arrayList.get(mid) <= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    }
}
